﻿#include <iostream>
using namespace std;

void printfArray(int *array, int length) {
    for (int i = 0; i < length; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

int quickArray1(int *array, int left, int right) {
    int i = left + 1;
    int j = right;
    int base = array[left];
    while (i < j) {
        while (i < j && base <= array[j]) j--;
        while (i < j && array[i] < base) i++;
        swap(array[i++], array[j--]);
    }

    int index = left;
    if (array[i] < base) {
        swap(array[left], array[i]);
        index = i;

    } else {
        swap(array[left], array[i - 1]);
        index = i - 1;
    }

    return index;
}

int quickArray2(int *array, int left, int right) {
    int i = left;
    int j = right;
    int base = array[left];

    while (i < j) {
        while (i < j && base < array[j]) j--;
        array[i] = array[j];
        while (i < j && array[i] <= base) i++;
        array[j] = array[i];
    }
    array[i] = base;

    return i;
}

void quickSort(int *array, int left, int right) {
    if (right <= left) {
        return;
    }

    int index = quickArray1(array, left, right);

    quickSort(array, left, index - 1);
    quickSort(array, index + 1, right);
}

int main() {
    int array[] = {4, 5, 1, 6, 7, 2, 3, 1, 5, 9, 0, 8, 7, 8, 9};
    int length = (sizeof(array)) / (sizeof(int));

    printf("排序前: ");
    printfArray(array, length);

    quickSort(array, 0, length - 1);

    printf("排序后: ");
    printfArray(array, length);

    return 0;
}